class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& inOrder) {
        int m = preOrder.size();
        int n = inOrder.size();
        if (m == 0 || n == 0) return nullptr;
        TreeNode* root = new TreeNode(preOrder[0]);
        for (int i = 0 ; i < n; i++) {
            if (preOrder[0] == inOrder[i]) {
                vector<int> leftpre(preOrder.begin() + 1, preOrder.begin() + i + 1);
                vector<int> leftin(inOrder.begin(), inOrder.begin() + i);
                root->left = reConstructBinaryTree(leftpre, leftin);
                vector<int> rightpre(preOrder.begin() + i + 1, preOrder.end());
                vector<int> rightin(inOrder.begin() + i + 1, inOrder.end());
                root->right = reConstructBinaryTree(rightpre, rightin);
            }
        }
        return root;
    }

    void dfs(TreeNode* root, int depth, vector<int>& res) {
        if (!root) return;
        if (depth == res.size())  res.push_back(root->val);
        dfs(root->right, depth + 1, res);
        dfs(root->left, depth + 1, res);
    }

    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        TreeNode* root = reConstructBinaryTree(preOrder, inOrder);
        vector<int> res;
        dfs(root, 0, res);
        return res;
    }
};